package com.fengye.algorithms.alibaba;

import com.fengye.algorithms.leecode.common.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author fengye
 * @Date 2023/4/11 9:52
 **/
public class FindStartCycle29 {
    public ListNode findStartCycle(ListNode head) {
        if(head == null) {
            return null;
        }

        if(head.next == null) {
            return null;
        }

        ListNode fast = head.next;
        ListNode slow = head;
        while (slow != fast) {
            // 说明没有环
            if(fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }

        Set<ListNode> set = new HashSet<>();
        slow = head;
        while (slow != null) {
            // 第一次出现的位置
            if(set.contains(slow)) {
                break;
            }
            set.add(slow);
            slow = slow.next;
        }
        set = null;
        return slow;
    }
}
